package lecode;

/**
 *
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 *请必须使用时间复杂度为 O(log n) 的算法。
 * 示例 1:
 *
 * 输入: nums = [1,3,5,6], target = 5
 * 输出: 2
 * 示例 2:
 *
 * 输入: nums = [1,3,5,6], target = 2
 * 输出: 1
 * 示例 3:
 *
 * 输入: nums = [1,3,5,6], target = 7
 * 输出: 4
 */
public class 搜索插入位置35 {

    public static void main(String[] args) {
        int[] nums1 = {1,3,5,6};
//        System.out.println(searchInsert(nums1,2));
//        System.out.println(searchInsert(nums1,7));
        System.out.println(searchInsert2(nums1,4));
        System.out.println(searchInsert2(nums1,2));
        System.out.println(searchInsert2(nums1,7));

    }


    /**
     * 暴力解法
     * 如果目标值大于最大值 那么目标值的下标=数组长度
     * 其他情况： 目标值小于等于第一个大于它的值就是目标值下标
     */
    public static int searchInsert(int[] nums, int target) {
        int index = 0;
        if (nums[nums.length-1] < target){
            return nums.length;
        }
        for (int i = 0; i < nums.length; i++) {
            if (target <= nums[i]){
                index = i;
                break;
            }
        }
        return index;
    }


    /**
     * 二分法
     * 选取初始下标 mind = left + (right - left) / 2
     * 左指针放在0 右指针放在末尾  插入4
     *  1     3       5     6
     *  l     m             r
     * 1      l             r   m=0+(3-0)/2 =1 -> 4>3 ->  l = m+1
     * 2              l=r     m=2+(3-2)/2 =2 -> 4<5 ->  < r = m
     * 3     l !< r 退出循环  ->  nums[left] < target ? left +1 : left;
     *
     * 末尾放7
     *  1     3       5       6    7
     *  l     m               r
     * 1              l=m           7>3 -> l=m+1=2 -> m = 2 + (3 - 2) / 2 = 2
     * 2                      l=m=r  7>5 -> l=m+1=3 -> m = 3 + 0 =3
     * 3                      l=r 退出循环
     * nums[left] < target  return left + 1
     */
    public static int searchInsert2(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right){
            int min = left + (right - left) / 2;
            if (target == nums[min]){  //与目标值相等 直接返回
              return min;
            }else if (target < nums[min]){ //目标值小min值 右边界等于 min - 1,左边界值不变
                right = min ;
            }else { //如果目标值大于min值，左边界值等于 min + 1，右边界值不变
                left = min + 1;
            }
        }
        return nums[left] < target ? left +1 : left;
    }




}
